package code1.graph;

import java.util.LinkedList;
import java.util.Queue;

public class P695 {

    int n,m;
    int ans=0;
    boolean[][] visited;
    int[][] go={{1,0},{-1,0},{0,-1},{0,1}};

    int bfs(int x,int y,int[][] grid){
        Queue<int[]> queue=new LinkedList<>();
        visited[x][y]=true;
        queue.offer(new int[]{x,y});
        int cnt=1;
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            for(int i=0;i<4;i++){
                int nextx=point[0]+go[i][0];
                int nexty=point[1]+go[i][1];
                if(nextx>=0 && nextx<n && nexty>=0 && nexty<m && grid[nextx][nexty]==1 && !visited[nextx][nexty]){
                    visited[nextx][nexty]=true;
                    queue.offer(new int[]{nextx,nexty});
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public int maxAreaOfIsland(int[][] grid) {
        n=grid.length;
        m=grid[0].length;
        visited=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j] && grid[i][j]==1){
                    int cnt = bfs(i, j, grid);
                    ans=Math.max(cnt,ans);
                }
            }
        }
        return ans;
    }
}
